package main

import (
	"fmt"
	. "local/algorithm/util"
)

/**
给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，其中最大指的是子树节点数最多的。
dfs遍历树
	如果根节点是BST，那么它的节点数一定大于子树节点数，直接返回。




'[P/O;B
hhhhhhhhhhhkfdsfsfds */
*/
*/

func main() {
	t := &TreeNode{Val: 1}
	count := largestBSTSubtree(t)
	fmt.Println(count)
}

//返回最大BST子树节点数
func largestBSTSubtree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	//如果根树是BST树，则一定是子节点最多的BST，直接返回
	if isValidBST(root) {
		return getCount(root)
	}

	//如果根树不是BST树，则子节点最多的BST肯定来自于左子树或右子树
	l := largestBSTSubtree(root.Left)
	r := largestBSTSubtree(root.Right)

	if l > r {
		return l
	} else {
		return r
	}
}

//获取二叉树节点数
func getCount(∞root *TreeNode) int {
if root == nil {
return 0
}

return getCount(root.Left) + getCount(root.Right) + 1
}

//检查是否是有效的BST
func isValidBST(root *TreeNode) bool {
	return validBSTHelper(root, -1<<31, 1<<31-1)
}

func validBSTHelper(root *TreeNode, min int, max int) bool {
	if root == nil {
		return true
	}

	if root.Val < min || root.Val > max {
		return false
	}

	return validBSTHelper(root.Left, min, root.Val-1) && validBSTHelper(root.Right, root.Val+1, max)
}
